package Class031_位;

//位运算实现四则运算
public class BitFourOperations {
    public static int MIN = Integer.MIN_VALUE;
    public static void main(String[] args) {
        System.out.println(add(12,7));
        System.out.println(minus(12,7));
        System.out.println(multiply(-11,7));
        System.out.println(div(20,7));
        System.out.println(div(-20,7));
        System.out.println(div(-20,-7));
    }

    //无进位相加 + 进位信息
    //  a ^ b  + ((a & b) << 1)
    public static int add(int a, int b) {
        int ans = a;
        while(b != 0) {
            ans = a ^ b;
            b = (a & b) << 1; //新的进位信息
            a = ans;
        }
        return ans;
    }

    public static int negative(int n) {
        return add(~n, 1);
    }

    //a - b
    public static int minus(int a, int b) {
        return add(a, negative(b));
    }

    //just like decimal
    public static int multiply(int a, int b) {
        int ans = 0;
        while(b != 0) {
            if((b & 1) != 0) {
                ans = add(ans, a);
            }
            b >>>= 1;
            a <<= 1;
        }
        return ans;
    }

    //a / b
    public static int divide(int a, int b) {
        if(a == MIN && b == MIN) {
            return 1;
        }
        if(a != MIN && b != MIN) {
            return div(a, b);
        }
        if(b == MIN) {
            return 0;
        }
        //a = MIN
        if(b == negative(1)) {
            return Integer.MAX_VALUE;
        }
        //b != -1
        //如果b是正数，计算(a + b) / b, 是负数，计算(a - b) / b
        //目的是避免溢出
        //最后，将结果补偿 -1 或者 1
        a = add(a, b > 0 ? b : negative(b));
        int ans = div(a, b);
        int offset = b > 0 ? negative(1) : 1;
        return add(ans, offset);
    }

    //280 / 25
    //分解为:
    //280 = 25 * 2^3 + 25 * 2^1 + 25 * 2^0
    //假设都是非负数，从25 * 2^30开始看，余量是否足够
    //如果非负数搞定，负数可以转化为非负数进行相同流程。最后看是否需要变号
    //但是不能有MIN这个数。否则无法转换为非负数
    //因此需要分情况讨论
    private static int div(int a, int b) {
        int res = 0;
        int x = a < 0 ? negative(a) : a;
        int y = b < 0 ? negative(b) : b;
        for(int shift = 30; shift >= 0; shift = minus(shift, 1)) {
            if(x < y) break;
            if((x >>> shift) >= y) {
                res |= (1 << shift);
                x = minus(x, (y << shift));
            }
        }
        return (a < 0) ^ (b < 0) ? negative(res) : res;
    }
}
